package leetcode_1_200;

import node.ListNode;
import node.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_109 {
    public static void main(String[] args) {
//        TreeNode treeNode = sortedListToBST(new ListNode(-10, new ListNode(-3,
//                new ListNode(0, new ListNode(5, new ListNode(9))))));
//        TreeNode treeNode1 = sortedListToBST(null);
//        TreeNode treeNode2 = sortedListToBST(new ListNode(1));
        TreeNode treeNode2 = sortedListToBST(new ListNode(1, new ListNode(3)));
    }
    private static TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        List<TreeNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null){
            list.add(new TreeNode(cur.val));
            cur = cur.next;
        }
        f(list, (list.size() - 1) / 2,0,  list.size() - 1);
        return list.get((list.size() - 1) / 2);
    }
    private static void f(List<TreeNode> list,int m, int s, int e){
        if (s < 0 || e >= list.size() || s >= e)
            return;
        int lm = (s + m - 1) / 2;
        if (lm < m && lm >= s){
            list.get(m).left = list.get(lm);
            f(list, lm, s, m - 1);
        }

        int rm = (m + 1 + e) / 2;
        if (rm > m && rm <= e){
            list.get(m).right = list.get(rm);
            f(list, rm, m + 1, e);
        }
    }
}
